#include <bits/stdc++.h>
using namespace std;
// 进行环形链表的模拟

struct Node
{
    Node(int v) : val(v) {}
    int val;
    Node *next;
};
class Solution1
{
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param n int整型
     * @param m int整型
     * @return int整型
     */
    int LastRemaining_Solution(int n, int m)
    {
        Node *head = nullptr;
        Node *curnode = nullptr;
        Node *prev = nullptr;
        // 创建循环单链表
        for (int i = 0; i < n; i++)
        {
            curnode = new Node(i);
            if (i == 0)
            {
                head = curnode;
                prev = curnode;
                continue;
            }
            prev->next = curnode;
            prev = curnode;
        }
        curnode->next = head;
        prev = curnode;
        curnode = head;
        while (curnode->next != curnode)
        {
            int count = 0;
            while (count != m - 1)
            {
                count++;
                prev = curnode;
                curnode = curnode->next;
            }
            prev->next = curnode->next;
            curnode = prev->next;
        }
        return curnode->val;
    }
};
// 进行数组的模拟 使用标记数组进行我们的判断

#define N 5001
class Solution2
{
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param n int整型
     * @param m int整型
     * @return int整型
     */
    bool check[5001]={false};
    int LastRemaining_Solution(int n, int m)
    {
       int curindex=0;
       int count=n;
       int ret;
       while(count!=1)
       {
            int tem=m-1;
            while(tem)
            {
                curindex=(curindex+1)%n;
                if(check[curindex]==false) tem--;
            }
            check[curindex]=true;
            count--;
            //更新我们报数的位置
            while(check[curindex]==true&&count!=1) curindex=(curindex+1)%n;
       }
       for(int i=0;i<n;i++) if(check[i]==false) ret=i;
       return ret;
    }
};

// 进行动态规划 思考下标映射的关系 dp[n][m]代表的是人 数为n个报数为m的获胜者 下面就是进行对应下标的映射
// 对于该题我们思考就是dp[n]就是人数为n的时候 报数为m此时的获胜者